package org.basis.algorithm.sort.practice;

import org.basis.algorithm.common.SortUtil;

/**
 * 冒泡排序
 *
 * @author Mr_wenpan@163.com 2021/12/06 20:48
 */
public class SortPractice01 {

    public static void main(String[] args) {
        final int maxSize = 100;
        final int maxValue = 100;
        final int count = 10000;

//        int[] arr = new int[]{1, 7, 8, 4, 3, 2, 9, 80, 1, 2, 5};

        // 使用对数器校验排序结果的正确性
        for (int i = 0; i < count; i++) {
            int[] arr = SortUtil.generateRandomArray(maxSize, maxValue);
            int[] array = SortUtil.copyArray(arr);
            SortUtil.comparator(array);
//            process(arr);
//            insertionSort(arr);
//            selectionSort(arr);
//            mergeSort(arr);
            bubbleSort(arr);
//            quickSort(arr);
            if (!SortUtil.isEqual(arr, array)) {
                System.out.println("两个数组不相等，退出.");
                break;
            }
        }

    }

    // 冒泡
    public static void sort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    SortUtil.swap(j, j + 1, arr);
                }
            }
        }
    }

    // 插入排序
    public static void sort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 对于i位置依次往前找到他合适的位置
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    SortUtil.swap(j, j - 1, arr);
                }
            }
        }

    }

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
    }

    private static void process(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 大的数依次向后冒泡
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    SortUtil.swap(j, j + 1, arr);
                }
            }
        }
    }

    private static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 选择第i个数，一直向前找到他合适的位置
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j - 1] > arr[j]) {
                    SortUtil.swap(j, j - 1, arr);
                }
            }
        }
    }

    private static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            int minPosition = i;
            for (int j = i; j < arr.length; j++) {
                // 找出值最小的位置
                if (arr[minPosition] > arr[j]) {
                    minPosition = j;
                }
            }
            // 每轮内层循环选出一个最小的
            SortUtil.swap(i, minPosition, arr);
        }
    }

    private static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int left, int right) {
        // base case
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int p = left;
        int q = mid + 1;
        int i = 0;

        // 都不越界的情况下，谁小拷贝谁
        while (p <= mid && q <= right) {
            if (arr[p] < arr[q]) {
                help[i] = arr[p];
                p++;
                i++;
            } else {
                help[i] = arr[q];
                q++;
                i++;
            }
        }

        // 有一边越界了
        while (p <= mid) {
            help[i] = arr[p];
            i++;
            p++;
        }
        while (q <= right) {
            help[i] = arr[q];
            i++;
            q++;
        }

        // 拷贝回原数组
        for (int k = 0; k < help.length; k++) {
            arr[left + k] = help[k];
        }
    }

    private static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        doQuickSort(arr, 0, arr.length - 1);
    }

    private static void doQuickSort(int[] arr, int left, int right) {
        // base case
        if (left >= right) {
            return;
        }
        int[] partition = partition(arr, left, right);
        doQuickSort(arr, left, partition[0]);
        doQuickSort(arr, partition[1], right);
    }

    private static int[] partition(int[] arr, int left, int right) {
        int p = left - 1;
        int q = right;
        int index = left;

        while (index < q) {
            if (arr[index] > arr[right]) {
                // index不++
                SortUtil.swap(index, --q, arr);
            } else if (arr[index] < arr[right]) {
                // index向前走一步，左区向前扩一步
                SortUtil.swap(index++, ++p, arr);
            } else {
                index++;
            }
        }

        // 交换最后一个元素
        SortUtil.swap(right, q, arr);

        return new int[]{p, q};
    }

}
